7024. Red and black

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can't move on red tiles, he can move only on black tiles.

Write a program to count the number of black tiles which he can reach by repeating the moves described above.

Input. Consists of multiple data sets. A data set starts with a line containing two positive integers w и h (w, h ≤ 20) – the numbers of tiles in the x- and y-directions, respectively.

There are h more lines in the data set, each of which includes w characters. Each character represents the color of a tile as follows.

· '.' – a black tile;

· '#' – a red tile;

· '@' – a man on a black tile(appears exactly once in a data set);

The end of the input is indicated by a line consisting of two zeros.

Output. For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

Sample input	Sample output
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0	45 59 6 13

SOLUTION

graphs – dfs - grids

Algorithm analysis

Start the depth first search from the black tile where the person is standing. Move only along the black cells, counting their number.

Algorithm realization

The given maze will be stored in a two dimensional character array m.

#define MAX 22

char m[MAX][MAX];

Functon dfs implements the depth first search from the point (i, j).

void dfs(int i, int j)

{

If the coordinates of the point go beyond the boundaries of the room, end the search.

if ((i < 0) || (i >= h) || (j < 0) || (j >= w)) return;

If the cell (i, j) contains not a black tile, then also end the search.

if (m[i][j] == '#') return;

Otherwise, mark the cell visited (for example, we assume that a red tile appears in it), increase the number of passed cells c by 1.

m[i][j] = '#'; c++;

Next go left to (i, j – 1), right to (i, j + 1), up to (i – 1, j) and down to (i + 1, j).

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

The main part of the program. Read the maze into a two dimensional character array m. In the variable c count the number of cells through which a person can pass.

while(scanf("%d %d\n",&w,&h), w + h)

{

for(с = i = 0; i < h; i++) gets(m[i]);

Find a tile where a person stands. Start the depth first search from it.

for(i = 0; i < h; i++)

for(j = 0; j < w; j++)

if (m[i][j] == '@') dfs(i,j);

Print the number of reachable tiles.

printf("%d\n",c);

}

Java realization

import java.util.*;

//import java.io.*;

public class Main

{

static char m[][];

static int h, w, c;

static void dfs(int i, int j)

{

if ((i < 0) || (i >= h) || (j < 0) || (j >= w)) return;

if (m[i][j] == '#') return;

m[i][j] = '#'; c++;

dfs(i-1,j); dfs(i+1,j);

dfs(i,j-1); dfs(i,j+1);

}

public static void main(String[] args) //throws IOException

{

Scanner con = new Scanner(System.in);

//Scanner con = new Scanner(new FileReader ("7024.in"));

while(true)

{

w = con.nextInt();

h = con.nextInt();

if (w == 0 && h == 0) break;

c = 0;

m = new char[h][w];

for(int i = 0; i < h; i++)

m[i] = con.next().toCharArray();

for(int i = 0; i < h; i++)

for(int j = 0; j < w; j++)

if (m[i][j] == '@') dfs(i,j);

System.out.println(c);

}

con.close();

}

}